---
title: "残垣断壁"
created: 2025-11-28
tags:
  - 算法
---

# 残垣断壁

## 题目 [残垣断壁](https://www.acwing.com/problem/content/5568/)

![[image-a5c36554.png]]

## 思路分析

考前最后一次周赛的第二题

如果不想太多的话就完全是板子题 拿来练一下手

其实可以发现 题目说不存在悬空的情况 所以一个块能与另一个块相连 则它们的底部是一定相连的 所以只需要枚举最后一行 看有多少个连续的B即可
看有多少段连续的B 只需要 统计第一个B出现的次数（前面是空或者是.即为第一个B）

直接洪水填充其实也很容易 都一样都一样

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=110;

char g[N][N];

bool st[N][N];

int n,m;

int res=0;

int dx[4]={-1,0,1,0};

int dy[4]={0,1,0,-1};

bool isVaild(int x,int y){

	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && !st[x][y];

}

void dfs(int x,int y){

	for(int i=0;i<4;i++){

		int nx=x+dx[i],ny=y+dy[i];

		if(isVaild(nx,ny) && (g[nx][ny]=='B')){

			st[nx][ny]=true;

			dfs(nx,ny);

		}

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=0;i<n;i++){

		cin>>g[i];

	}

	for(int i=0;i<n;i++){

		for(int j=0;j<m;j++){

			if(g[i][j]=='B' && !st[i][j]){

				st[i][j]=true;

				dfs(i,j);

				res++;

			}

		}

	}

	cout<<res<<endl;

	return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=110;

char g[N][N];

int n,m;

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=0;i<n;i++)

		cin>>g[i];

	int res=0;

	for(int i=0;i<m;i++){

		if(g[n-1][i]=='B' && (!i || g[n-1][i-1]=='.'))

			res++;

	}

	cout<<res<<endl;

 	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[山峰和山谷|山峰和山谷]] 🏠 [[00-刷题理模型]] ➡️ [[求细胞数量|求细胞数量]]